// 给定一个二叉树，返回其节点值的锯齿形层序遍历
// 锯齿形层序遍历：从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行
// 思路，层序遍历
// 用一个遍历来判断是奇数还是偶数层，奇数层向末尾添加元素，如果偶数层向头部添加元素

function zigzagLevelOrder(root) {
    let result = []
    let queue = []
    if (root) {
        queue.push(root)
    }
    let odd = true
    while (queue.length) {
        let level = []
        let len = queue.length
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            if (odd) {
                level.push(node.val)
            } else {
                level.unshift(node.val)
            }          
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
        result.push(level)
        odd = !odd
    }
    return result
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
        },
    },
};
console.log(zigzagLevelOrder(root))